---
title: "354. Russian Doll Envelopes"
created: 2025-12-20
---
# 354. Russian Doll Envelopes

## 题目 [**354. Russian Doll Envelopes**](https://leetcode.com/problems/russian-doll-envelopes/)

![[image-71f62a68.png]]

## 思路分析

能否贪心？用优先队列 按长、宽共同排序 先拿到最大的作为cur 看下一个能否嵌入 不能就再看下一个 cur会更新成最新的 cnt++

```java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length == 0)   return 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            if(a[0]!=b[0]){
                return b[0]-a[0];
            }else{
                return b[1]-a[1];
            }
        });

        for(int[] env:envelopes){
            pq.offer(env);
        }

        int[] cur = pq.poll();
        int cnt = 1;

        while(!pq.isEmpty()){
            int[] next = pq.poll();
            if(next[0]<cur[0] && next[1]<cur[1]){
                cnt++;
                cur=next;
            }
        }
        return cnt;
    }
}
```

![[image-739f57be.png]]

假设输入是：`[[10, 2], [5, 10], [4, 9], [3, 8]]`

1. **当前代码执行流程**：
   - **排序后 PQ**：`[10, 2], [5, 10], [4, 9], [3, 8]`
   - 取出 `cur` = `[10, 2]` (因为它的宽 10 最大)。
   - 取出 `next` = `[5, 10]`。判断：`5 < 10` (true) 但 `10 < 2` (false)。**不能放入，丢弃**。
   - 取出 `next` = `[4, 9]`。判断：`4 < 10` (true) 但 `9 < 2` (false)。**不能放入，丢弃**。
   - 取出 `next` = `[3, 8]`。判断：`3 < 10` (true) 但 `8 < 2` (false)。**不能放入，丢弃**。
   - **最终输出结果**：`1`
2. **正确的最优解**：
   - 我们不选那个看起来最大的 `[10, 2]`。
   - 我们可以选 `[5, 10] -> [4, 9] -> [3, 8]`。
   - **正确结果**：`3`

**结论**： 贪心策略在于“**只顾眼前最大**”。一旦选了一个**“偏科”**的信封（比如特别宽但特别矮的 `[10, 2]`），它就会把后面所有“瘦高”个子的潜在答案全部卡死。

到这里其实就知道 应该是个dp问题

最长上升子序列模型的二维变种

可以通过巧妙的排序，将二维问题降维成一维问题：

1. 巧妙的排序规则（核心！）

- **按宽度 (**\(w\)**) 升序排序**：保证后面的信封宽度肯定比前面的大（或相等）。
- **如果宽度相同，按高度 (**\(h\)**) 降序排序**：这是一个非常关键的技巧！

为什么要让高度降序？

假设有两个信封 [3, 3] 和 [3, 4]。

- 如果我们按高度升序排：`[3, 3], [3, 4]`。在计算 LIS 时，`3` 和 `4` 会形成递增序列，导致我们误判 `[3, 3]` 可以放入 `[3, 4]`，但这在物理上是不可能的（宽度相同不能套娃）。
- 如果我们按高度降序排：`[3, 4], [3, 3]`。在计算 LIS 时，`3` 无法接在 `4` 后面增加长度，从而**避免了同一宽度下选择多个信封**的情况。

2. 一维 LIS

排序后，我们只需要对 **高度 (**\(h\)**)** 数组求 **最长递增子序列** 的长度即可。因为宽度已经是升序的了，只要高度递增，信封就能套进去。

```java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if(n==0)    return 0;
        Arrays.sort(envelopes,(a,b)->{
            if(a[0]==b[0]){
                return b[1]-a[1];//h降序
            }else{
                return a[0]-b[0];//w升序
            }
        });

        int[] f = new int[n];
        Arrays.fill(f,1);
        int res = 1;

        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                // 因为已经按宽度排好序了(且同宽按高度降序)，
                // 所以只要 envelopes[j][1] < envelopes[i][1]，
                // 就意味着 envelopes[j] 一定能放进 envelopes[i]
                if(envelopes[j][1]<envelopes[i][1]){
                    f[i]=Math.max(f[i],f[j]+1);
                }
            }
            res=Math.max(res,f[i]);
        }
        return res;
    }
}
```

![[image-d2198c51.png]]

注意：由于 \(N\) 高达 \(10^5\)，普通的 \(O(N^2)\) DP 解法会超时，必须使用 **二分查找优化** 的贪心 LIS 解法，复杂度为 \(O(N \log N)\)。

## 代码实现

```java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if(n==0)    return 0;
        Arrays.sort(envelopes,(a,b)->{
            if(a[0]==b[0]){
                return b[1]-a[1];//h降序
            }else{
                return a[0]-b[0];//w升序
            }
        });


        int[] f = new int[n];
        int res = 0;

        for (int[] env : envelopes) {
            int h = env[1];
            
            // 贪心策略：
            // 情况 1: 如果当前高度 h 比 f 数组中最大的元素（最后一个）还要大，直接追加
            if (res == 0 || h > f[res - 1]) {
                f[res] = h;
                res++;
            } 
            // 情况 2: 否则，二分找到第一个 >= h 的位置进行替换
            else {
                // 在 f 数组的 [0, res-1] 范围内查找
                int index = Search(f, 0, res - 1, h);
                f[index] = h;
            }
        }

        return res;
    }

    private int Search(int[] nums, int l, int r, int k) {
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return r;
    }

}
```

## 同类题型

## 视频讲解